package com.datastructure.search.self;

import java.util.ArrayList;
import java.util.List;

public class DivideSearch {
    public static void main(String[] args) {

    }

    public static List<Integer> findTargetLocation(int[] arr,int left,int right,int target){
        List<Integer> res = new ArrayList<>();
        int mid = (right-left)/2;
        if(arr[mid]<target){
            //往右查询
            return findTargetLocation(arr,mid+1,right,target);
        } else if(arr[mid]>target){
            //往左查询
            return findTargetLocation(arr,left,mid-1,target);
        } else {
            int temp = mid-1;
            while (temp >= 0 && arr[temp] == target) {
                res.add(arr[temp]);
                temp--;
            }
            res.add(arr[mid]);
            temp = mid + 1;
            while ((temp <= (arr.length - 1)) && (arr[temp] == target)) {
                res.add(arr[temp]);
                temp++;
            }
        }
        return res;
    }
}
